We provide an algorithm with regret O(CdloglogT) for contextual pricing with C corrupted rounds, improving over the previous bound of O(d3Clog2(T)) of Krishnamurthy et al. (2020). The result is based on a reduction that calls the uncorrupted algorithm as a black-box, unlike the previous approach that modifies the inner workings of the uncorrupted algorithm. As a result, it leads to a conceptually simpler algorithm. Finally, we provide a lower bound ruling out a O(C +dloglogT)algorithm. This shows that robustifying contextual pricing is harder than robustifying contextual search with ϵ-ball losses, for which it is possible to design algorithms where corruptions add only an extra additive term C to the regret.

Online multiclass classification is a ubiquitous problem in machine learning.

We wish to2 learn a hiddend-dimensional valuew . Every round, we are presented with a3 subset Xt Rd of possible actions.

We wish to learn a hiddend-dimensional valuew . Every round, we are presented with a subset Xt Rd of possible actions.

We consider the problem of multi-class classification, where a stream of adversari-ally chosen queries arrive and must be assigned a label online.

We consider the problem of multi-class classification, where a stream of adversari-ally chosen queries arrive and must be assigned a label online.

Consider the following problem faced by a geographical query service (e.g.

We study the problem of contextual search, a generalization of binary search in higher dimensions, in the adversarial noise model. Let $d$ be the dimension of the problem, $T$ be the time horizon and $C$ be the total amount of adversarial noise in the system. We focus on the $\epsilon$-ball and the absolute loss. For the $\epsilon$-ball loss, we give a tight regret bound of $O(C + d \log(1/\epsilon))$ improving over the $O(d^3 \log(1/\epsilon) \log^2(T) + C \log(T) \log(1/\epsilon))$ bound of Krishnamurthy et al (Operations Research '23). For the absolute loss, we give an efficient algorithm with regret $O(C+d \log T)$. To tackle the absolute loss case, we study the more general setting of Corruption-Robust Convex Optimization with Subgradient feedback, which is of independent interest. Our techniques are a significant departure from prior approaches. Specifically, we keep track of density functions over the candidate target vectors instead of a knowledge set consisting of the candidate target vectors consistent with the feedback obtained.